In this article we'll explain the basics of cryptography. We'll use email as our sample application, because that's an intuitive use. Let's start with secret-key and public-key encryption.
Secret-Key Cryptography
The concept of secret-key cryptography is probably familiar. You start with an encryption algorithm, such as IDEA or DES, and a secret key. If you take a message, the plain text and encrypt it with the key, you get ciphertext. If you take the ciphertext and decrypt it with the key, you get back the original plain text.
To send you a message, I encrypt it using our secret key, and send you the resulting ciphertext. You decrypt it using our secret key, so you can read the message, but no one else can. Anyone else who intercepts a copy of the ciphertext is stuck because they don't know the key, so they can't decrypt the message.
Secret-key cryptography is also called symmetric-key cryptography, because we use the same key to encrypt and decrypt the message. Note that the key is the secret. The encryption algorithm (how you encrypt and decrypt) is public knowledge, but nobody can decrypt a message without knowing the key that encrypted it.
In a way, it's like the lock on your door. Everybody knows how locks work. That's no secret but to open a particular door, you need the key to that particular lock, and that's the secret. Can you pick a lock without the key? It depends on the strength (in the abstract sense) of the technique used by the lock. The same is true of computer encryption algorithms. Some, like IDEA and DES, are essentially unbreakable because you'd have to try every possible key until you find the one that works. Others, like those in word processors, ZIP, and the like, are toy algorithms for which it's possible to find techniques that break them without trying every possible key.
Public-Key Cryptography
Public-key cryptography is just as simple, but it uses a pair of keys. Public-key cryptography is also called asymmetric-key cryptography, because we use different keys to encrypt and decrypt the message.
Start with an encryption algorithm, like RSA, and a pair of keys called the public and private keys. If you take a message and encrypt it using the public key, you get ciphertext. If you take the ciphertext and decrypt it using the private key, you get back the original plain text.
To send you a message, I encrypt it using your public key, and send you the resulting ciphertext. You decrypt it by using your private key, so you can read the message, but no one else can, because you tell no one your private key.
In the other direction, to send me a message, you encrypt it using my public key and send me the ciphertext. I decrypt it using my private key. In other words, you have a key pair, and I have a key pair, unlike secret-key cryptography, where we used the same key for mail in both directions.
Sounds like a pain, aren't there too many keys?
Isn't it simpler to use secret-key cryptography, with only one key, instead of public-key cryptography, where we need two pairs of keys? Not really. Consider what happens as we add more and more people to our group.
Let's say we've got 100 people in our group, with enough keys to allow anyone to send an encrypted message to anyone else so only the intended recipient can decrypt and read it. What happens when we add the 101st person to the group?
With secret-key cryptography, the new person must visit each of the 100 people in the group to establish 100 new keys, one for email between the new person and each of the 100 people already in the group. We can't use email to send the new keys, because the keys must be secret (normally, we'd encrypt something to keep it secret, but we can't encrypt the keys themselves because we don't yet share a key with the recipient).
With public-key cryptography, the new person sends his public key to everyone, and everybody else sends their public keys to the new person. There's no chicken-and-egg problem because the public keys are, by definition, public. In fact, he can simply ask one person for the entire set of 100 public keys, rather than asking for each individually.
By using public-key cryptography, we make it much simpler to distribute keys. There's no, "How can I securely send a key before I've sent a key to be able to encrypt the key I want to send securely?" problem. And we need only one new key, because everyone uses the same public key to send a confidential message to the new person; we don't need a new secret key for each pair of people. And we can use a centralized public key directory, if we wish, unlike the individual databases of secret keys that must be managed secretly by each person.
Digital signatures
If I receive a message that claims to be from you, how can I be sure you sent it? If there were a signature, I could verify that the message really came from you. Of course, this signature must be more sophisticated than the kind of signatures we use on paper; you can copy an ordinary signature, but our digital signature must be uncopyable.
Will encryption alone solve our problem? No. With a public-key cryptosystem, anyone can encrypt a message they send me. That's the whole point, of course, but a side effect is that I have no way of knowing for certain who actually wrote the message.
Would secret-key encryption work better? Not really. If I get an encrypted message from you, I can infer that you sent it, because I know it was sent by someone who knows the secret key, and only you and I know the key. But that doesn't really solve the problem, because there's still no signature that I can store or show someone else.
Let's consider a paper analogy. If I send you a memo saying, Go ahead and buy the 737; think of all the money we'll save on airfare. I'll pay for it from my budget, you'll probably forward a copy of my message to your purchasing department to prove that I offered to pay for it. Or let's say I write you a cheque. You forward the cheque to your bank.
In both cases, you check my signature to make sure I really sent the message, and you forward the message to someone else, who checks my signature to make sure you didn't write the message or cheque yourself.
Public-key cryptography to the rescue
If you encrypt a message with a public key, only the corresponding private key can decrypt it. It turns out that the reverse is true as well if you encrypt a message with a private key, only the corresponding public key can decrypt it. And this gives us what we need for a signature.
First, I send you the message. Next, I encrypt another copy of the message using my private key, and send you the ciphertext; it's my signature.
To check my signature, you decrypt the ciphertext using my public key, and compare it to the message I sent you. If it matches, you know I must have sent it. After all, you successfully decrypted it using my public key, which means it must have been encrypted using my private key. Because I'm the only one who knows my private key, I must have been the one who generated the signature.
And not only does that prove that the message really came from me, it lets you prove to someone else that you got the message from me just send them the message and the signature, and they can verify the signature if they have a copy of my public key.
And not only that, but it verifies the integrity of the message. Unlike a paper signature, a digital signature is tied to the message that was signed. If anyone makes a change to the message, the signature won't check, and you'll know it wasn't what I originally sent.
